package cn.gadshawn.recommend

import org.junit.Test

// 一、动态规划
class AlgorithmDynamicProgramming {

    /**
     * LC: 53.最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 子数组是数组中的一个连续部分。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * 示例 2：
     *
     * 输入：nums = [1]
     * 输出：1
     * 示例 3：
     *
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     *
     *
     * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
     */
    @Test
    fun test_maxSubArray() {
        val nums = intArrayOf(-2,1,-3,4,-1,2,1,-5,4)
        println(maxSubArray(nums))
        println(maxSubArray_2(nums))
    }

    /**
     * 找出子问题：以nums[i]为结尾的数组，最大值dp[i]是多少？
     * 状态转移方程：
     *      dp[i-1] > 0,  dp[i] = dp[i-1] + nums[i]
     *      dp[i-1] <= 0, dp[i] = nums[i]
     * 初始值：dp[0] = nums[0]
     */
    fun maxSubArray(nums: IntArray): Int {
        val len = nums.size
        val dp = IntArray(len)
        dp[0] = nums[0]
        var max = dp[0]
        for (i in 1 until  len) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
            if (max < dp[i]) max = dp[i]
        }
        return max
    }

    // 优化空间复杂度
    fun maxSubArray_2(nums: IntArray): Int {
        var pre = nums[0]
        var max = pre
        for (i in 1 until  nums.size) {
            pre = Math.max(pre + nums[i], nums[i])
            if (max < pre) max = pre
        }
        return max
    }

    /**
     * LC: 72.编辑距离
     * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     *
     *
     * 示例 1：
     *
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     * 示例 2：
     *
     * 输入：word1 = "intention", word2 = "execution"
     * 输出：5
     * 解释：
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     *
     *
     * 提示：
     *
     * 0 <= word1.length, word2.length <= 500
     * word1 和 word2 由小写英文字母组成
     */
    @Test
    fun test_minDistance() {
        val word1 = "horse"
        val word2 = "ros"
        println(minDistance(word1, word2))
    }

    fun minDistance(word1: String, word2: String): Int {
        val m = word1.length
        val n = word2.length
        if (m == 0) return n
        if (n == 0) return m
        val dp = Array(n + 1) { IntArray(m + 1) {0} }
        for (i in 1 ..  n) {
            dp[i][0] = i
            for (j in 1 .. m) {
                dp[0][j] = j
                if (word1[j - 1] == word2[i - 1]) {
                    dp[i][j] = dp[i-1][j-1]
                } else {
                    dp[i][j] = minOf(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                }
            }
        }
        printDp(word1, word2, dp)
        return dp[n][m]
    }

    fun printDp(word1: String, word2: String, dp: Array<IntArray>) {
        print("   ")
        for (c in word1) {
            print(" " + c)
        }
        println()
        for (n in 0 until dp.size) {
            if ( n >= 1) print(word2[n - 1])
            else print(" ")
            for (m in 0 until dp[0].size) {
                print(" " + dp[n][m])
            }
            println()
        }
    }

    /**
     * LC: 300.最长递增子序列
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     *
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * 示例 2：
     *
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * 示例 3：
     *
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 2500
     * -104 <= nums[i] <= 104
     *
     *
     * 进阶：
     *
     * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
     *
     */
    @Test
    fun test_lengthOfLIS() {
        println(lengthOfLIS(intArrayOf(10,9,2,5,3,7,101,18))) // 4
        println(lengthOfLIS(intArrayOf(0,1,0,3,2,3))) // 4
        println(lengthOfLIS(intArrayOf(7,7,7,7,7,7,7))) // 1
    }

    /**
     *          0   1   2   3   4   5   6   7
     * nums     10  9   2   5   3   7   101 18
     * dp       1
     *
     * dp[0] = 1
     * dp[1] = 1            9 < 10  +1
     * dp[2] = 1            2 < 10  +1
     * dp[3] = dp[2] + 1    5 > 2   +1
     * dp[4] = dp[2] + 1    3 > 2   +1
     *
     * max = maxOf(max, dp[i])
     */
    fun lengthOfLIS(nums: IntArray): Int {
        val len = nums.size
        val dp = IntArray(len)
        dp[0] = 1
        var max = dp[0]
        for (i in 0 until len) {
            var findSmaller = false
            for (j in i downTo 0) {
                if (nums[i] > nums[j]) {
                    dp[i] = maxOf(dp[j] + 1, dp[i])
                    findSmaller = true
                }
            }
            if (!findSmaller) {
                dp[i] = 1
            }
            max = maxOf(max, dp[i])
        }
        return max
    }

























}